#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>

using namespace std;

const int N = 10010;

int h[N], e[N], ne[N], w[N], idx;
bool st[N];
int dist[N];

typedef pair<int, int> PII;
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dijkstra(int u)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    dist[u] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({ 0,u });
    while (!pq.empty())
    {
        auto t = pq.top();
        pq.pop();

        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > w[i] + distance)
            {
                dist[j] = w[i] + distance;
                pq.push({ dist[j],j });
            }
        }
    }
}

int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
    memset(h, -1,sizeof h);
    memset(e, 0, sizeof e);
    memset(ne, 0, sizeof ne);
    memset(w, 0, sizeof w);
    idx = 0;
    for (int i = 0; i < edges.size(); i++)
        add(edges[i][0], edges[i][1], edges[i][2]),
        add(edges[i][1], edges[i][0], edges[i][2]);

    int nmin = INT_MAX, res = 0;
    for (int i = 0; i < n; i++)
    {
        dijkstra(i);
        int count = 0;
        for (int j = 0; j < n; j++)
        {
            if (dist[j] <= distanceThreshold) count++;
        }
        if (count <= nmin)
        {
            res = i;
            nmin = count;
        }
    }
    return res;
}


int main()
{
    vector<vector<int>> vv = { {0,1,3},{1,2,1},{1,3,4},{2,3,1} };
    cout << findTheCity(4, vv, 4) << endl;
    return 0;
}